#include "biTree.h"

/**
 * 功 能：
 *      创建并且初始二叉树 - 指针定义
 * 参 数：
 *      无
 * 返回值：
 *      无
 **/
void BiTree_Create(void)
{
    BiTNode *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9;

    p1 = (BiTNode *)malloc(sizeof(BiTNode));
    p2 = (BiTNode *)malloc(sizeof(BiTNode));
    p3 = (BiTNode *)malloc(sizeof(BiTNode));
    p4 = (BiTNode *)malloc(sizeof(BiTNode));
    p5 = (BiTNode *)malloc(sizeof(BiTNode));
    p6 = (BiTNode *)malloc(sizeof(BiTNode));
    p7 = (BiTNode *)malloc(sizeof(BiTNode));
    p8 = (BiTNode *)malloc(sizeof(BiTNode));
    p9 = (BiTNode *)malloc(sizeof(BiTNode));

    memset(p1, 0, sizeof(BiTNode));
    memset(p2, 0, sizeof(BiTNode));
    memset(p3, 0, sizeof(BiTNode));
    memset(p4, 0, sizeof(BiTNode));
    memset(p5, 0, sizeof(BiTNode));
    memset(p6, 0, sizeof(BiTNode));
    memset(p7, 0, sizeof(BiTNode));
    memset(p8, 0, sizeof(BiTNode));
    memset(p9, 0, sizeof(BiTNode));

    p1->data = 'A';
    p2->data = 'B';
    p3->data = 'C';
    p4->data = 'D';
    p5->data = 'E';
    p6->data = 'F';
    p7->data = 'G';
    p8->data = 'H';
    p9->data = 'I';

    /* 二叉树的关系式的创建 */
    p1->lchild = p2;
    p1->rchild = p3;
    p2->lchild = p4;
    p2->rchild = p5;
    p3->lchild = p6;
    p3->rchild = p7;

    p4->lchild = p8;
    p4->rchild = p9;

    /* 二叉树的遍历 */
    printf("Traversal_Before : ");
    RTraversal.prev(p1);
    putchar(10);
    printf("Traversal_Middle : ");
    RTraversal.middle(p1);
    putchar(10);
    printf("Traversal_Later  : ");
    RTraversal.post(p1);
    putchar(10);
    printf("Traversal_Level  : ");
    RTraversal.level(p1);
    putchar(10);

    printf("%s Finished! \n", __func__);
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 先序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Before(BiTNode *root)
{
    if (root == NULL)
        return;
    // 遍历根节点
    printf("%c ", root->data);
    // 遍历左子树
    Traversal_Before(root->lchild);
    // 遍历右子树
    Traversal_Before(root->rchild);
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Middle(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历左子树
    Traversal_Middle(root->lchild);
    // 遍历根节点
    printf("%c ", root->data);
    // 遍历右子树
    Traversal_Middle(root->rchild);
}
/**
 * 功 能：
 *      二叉树的递归遍历 - 后序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Later(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历左子树
    Traversal_Later(root->lchild);
    // 遍历右子树
    Traversal_Later(root->rchild);
    // 遍历根节点
    printf("%c ", root->data);
}

/**
 * 功 能：
 *      求出二叉树的深度/高度
 * 参 数：
 *      root：要求高度的树
 * 返回值：
 *      无 
 **/
int CounterTreeDepth(BiTNode *root)
{
    int left = 0;
    int right = 0;
    int value = 0;

    if (root == NULL)
    {
        value = 0;
        return value;
    }
    // 左子树的高度
    left = CounterTreeDepth(root->lchild);
    // 右子树的高度
    right = CounterTreeDepth(root->rchild);
    // 左子树的高度 或者 右子树高度 + 1
    value = 1 + (left > right ? left : right);

    return value;
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 第i层的遍历
 * 参 数：
 *      root：要遍历的树
 *      i   ：要遍历的层
 * 返回值：
 *      无 
 **/
void _Traversal_Level(BiTNode *root, int i)
{
    if (root == NULL || i == 0)
        return;
    if (i == 1)
    {
        printf("%c ", root->data);
        return;
    }
    _Traversal_Level(root->lchild, i - 1);
    _Traversal_Level(root->rchild, i - 1);
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 层序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Level(BiTNode *root)
{
    int i = 0;
    if (root == NULL)
        return;
    int dep = CounterTreeDepth(root); // BTreeDepth(root);
    for (i = 1; i <= dep; i++)
    {
        _Traversal_Level(root, i);
    }
}

fRTraversal RTraversal = {
    BiTree_Create,
    Traversal_Before,
    Traversal_Middle,
    Traversal_Later,
    Traversal_Level};
